"""
238. 除自身以外数组的乘积
给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
输入: [1,2,3,4]
输出: [24,12,8,6]
两个dp数组一个存储左侧的值一个存储右侧的值然后相乘
"""


class Solution:
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        dp1 = [1]
        dp2 = [1]
        l = len(nums)
        res = []
        for i in range(l-1):
            dp1.append(nums[i]*dp1[i])
            dp2.append(nums[-i-1]*dp2[i])
        for j in range(len(dp1)):
            res.append(dp1[j]*dp2[-j-1])
        return res

s=Solution()
print(s.productExceptSelf([1,2,3,4]))